/*
 * @lc app=leetcode.cn id=76 lang=cpp
 *
 * [76] 最小覆盖子串
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    unordered_map<char, int> ori, cnt;
    bool check()
    {
        for(auto& p:ori)
        {
            if(cnt[p.first] < p.second)
            {
                return false;
            }
        }
        return true;
    }
    string minWindow(string s, string t)
    {
        for (auto &c : t)
        {
            ori[c]++;
        }

        int l = 0, r = -1;
        int len = INT_MAX, ans_l = -1, ans_r = -1;

        while (r < int(s.size()))
        {
            if (ori.find(s[++r]) != ori.end())
            {
                cnt[s[r]]++;
            }
            while (check() && l <= r)
            {
                if (r - l + 1 < len)
                {
                    len = r - l + 1;
                    ans_l = l;
                }
                if(ori.find(s[l]) != ori.end())
                {
                    cnt[s[l]]--;
                }
                ++l;
            }
        }

        return ans_l == -1 ? "" : s.substr(ans_l, len);
    }
};
// @lc code=end
